fn main() {
    let l1 = Some(Box::new(ListNode {
        val: 2,
        next: Some(Box::new(ListNode {
            val: 4,
            next: Some(Box::new(ListNode { val: 3, next: None })),
        })),
    }));

    let l2 = Some(Box::new(ListNode {
        val: 5,
        next: Some(Box::new(ListNode {
            val: 6,
            next: Some(Box::new(ListNode { val: 4, next: None })),
        })),
    }));

    println!("{:#?}", l1);
    println!("{:#?}", l2);

    let res = Solution4::add_two_numbers(l1, l2);

    println!("{:#?}", res);
}

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

struct Solution;

impl Solution {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let v1 = Solution::list_to_vec(l1);
        let v2 = Solution::list_to_vec(l2);
        let mut bit = 0;
        let len = if v1.len() > v2.len() {
            v1.len()
        } else {
            v2.len()
        };
        let mut v3 = vec![];
        for i in 0..len {
            let val1 = if let Some(val) = v1.get(i) { *val } else { 0 };
            let val2 = if let Some(val) = v2.get(i) { *val } else { 0 };
            let sum = val1 + val2 + bit;
            bit = sum / 10;
            let sum = sum % 10;
            v3.push(sum);
        }
        if bit == 1 {
            v3.push(bit);
        }
        let len = v3.len();
        let mut result = None;
        for i in 0..len {
            let index = len - i - 1;
            let mut node = Some(Box::new(ListNode::new(v3[index])));
            node.as_mut().unwrap().next = result.take();
            result = node;
        }
        result
    }

    fn list_to_vec(list: Option<Box<ListNode>>) -> Vec<i32> {
        let mut result = vec![];
        let mut record = &list;
        while let Some(node) = record {
            result.push(node.val);
            record = &node.next;
        }
        result
    }
}

struct Solution2;

impl Solution2 {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut r1 = &l1;
        let mut r2 = &l2;
        let mut bit = 0;
        let mut reverse = None;
        loop {
            let val1 = if let Some(node1) = r1 {
                r1 = &node1.next;
                node1.val
            } else {
                0
            };
            let val2 = if let Some(node2) = r2 {
                r2 = &node2.next;
                node2.val
            } else {
                0
            };
            let mut sum = val1 + val2 + bit;
            bit = sum / 10;
            sum = sum % 10;
            let mut node = Some(Box::new(ListNode::new(sum)));
            node.as_mut().unwrap().next = reverse.take();
            reverse = node;
            if let None = r1 {
                if let None = r2 {
                    if bit == 1 {
                        let mut node = Some(Box::new(ListNode::new(bit)));
                        node.as_mut().unwrap().next = reverse.take();
                        reverse = node;
                    }
                    break;
                }
            }
        }
        let mut tmp = &reverse;
        let mut result = None;
        while let Some(list_node) = tmp {
            let mut node = Some(Box::new(ListNode::new(list_node.val)));
            node.as_mut().unwrap().next = result.take();
            result = node;
            tmp = &list_node.next;
        }
        result
    }
}

struct Solution3;

impl Solution3 {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut r1 = &l1;
        let mut r2 = &l2;
        let mut bit = 0;
        let mut reverse = None;
        loop {
            let (val1, val2) = if let Some(node1) = r1 {
                r1 = &node1.next;
                if let Some(node2) = r2 {
                    r2 = &node2.next;
                    (node1.val, node2.val)
                } else {
                    (node1.val, 0)
                }
            } else {
                if let Some(node2) = r2 {
                    r2 = &node2.next;
                    (0, node2.val)
                } else {
                    if bit == 1 {
                        let mut node = Some(Box::new(ListNode::new(bit)));
                        node.as_mut().unwrap().next = reverse.take();
                        reverse = node;
                    }
                    break;
                }
            };
            let mut sum = val1 + val2 + bit;
            bit = sum / 10;
            sum = sum % 10;
            let mut node = Some(Box::new(ListNode::new(sum)));
            node.as_mut().unwrap().next = reverse.take();
            reverse = node;
        }
        let mut tmp = &reverse;
        let mut result = None;
        while let Some(list_node) = tmp {
            let mut node = Some(Box::new(ListNode::new(list_node.val)));
            node.as_mut().unwrap().next = result.take();
            result = node;
            tmp = &list_node.next;
        }
        result
    }
}

struct Solution4;

impl Solution4 {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut r1 = &l1;
        let mut r2 = &l2;
        let mut bit = 0;
        let mut vec = vec![];
        let mut result = None;
        loop {
            let (val1, val2) = if let Some(node1) = r1 {
                r1 = &node1.next;
                if let Some(node2) = r2 {
                    r2 = &node2.next;
                    (node1.val, node2.val)
                } else {
                    (node1.val, 0)
                }
            } else {
                if let Some(node2) = r2 {
                    r2 = &node2.next;
                    (0, node2.val)
                } else {
                    if bit == 1 {
                        vec.push(bit);
                    }
                    let len = vec.len();
                    for i in 0..len {
                        let index = len - i - 1;
                        let mut node = Some(Box::new(ListNode::new(vec[index])));
                        node.as_mut().unwrap().next = result;
                        result = node;
                    }
                    break;
                }
            };
            let mut sum = val1 + val2 + bit;
            bit = sum / 10;
            sum = sum % 10;
            vec.push(sum);
        }
        result
    }
}
